package algorithm

import "fmt"

// 排序算法代码汇总

// 基于排序算法设定默认乱序数组
var defaultArray = []int{2, 1, 5, 70, 18, 64, 32, 128, 6, 9, 42, 44, 30}

// quickSort 快速排序
// @param array 数组
// @param first 第一个值
// @param last 最后一个值
func quickSort(array []int, first, last int) {
	// 定义当前数字节点
	localNumber := first
	// 左侧目标数字节点
	left := first
	// 右侧节点
	right := last
	// 如果当前节点 >= 右侧偏移节点则结束当前方法
	if first >= last {
		return
	}
	// 将大于array[localNumber]的都放到右边,小于array[localNumber]的都放在左边
	for first < last {
		// 如果a从左边开始,那么先从右边开始对比,即在右边获取比a小的
		for first < last {
			if array[last] >= array[localNumber] {
				last--
				continue
			}
			// 交换数据
			array[last], array[localNumber] = array[localNumber], array[last]
			localNumber = last
			break
		}
		for first < last {
			if array[first] <= array[localNumber] {
				first++
				continue
			}
			array[first], array[localNumber] = array[localNumber], array[first]
			localNumber = first
			break
		}
		quickSort(array, left, localNumber-1)
		quickSort(array, localNumber+1, right)
	}
}

// QuickSortDemo 快速排序演示
func QuickSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	quickSort(copyArray, 0, len(copyArray)-1)
	fmt.Println(copyArray)
}

// bubbleSort 冒泡排序
func bubbleSort(array []int) {
	for i := 0; i < len(array)-1; i++ {
		for j := i + 1; j < len(array); j++ {
			if array[i] > array[j] {
				array[i], array[j] = array[j], array[i]
			}
		}
	}
}

// BubbleSortDemo 冒泡排序演示
func BubbleSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	bubbleSort(copyArray)
	fmt.Println(copyArray)
}

// insertSort 插入排序
func insertSort(array []int) {
	for i := 0; i < len(array); i++ {
		for j := i; j > 0 && array[j-1] > array[j]; j-- {
			array[j], array[j-1] = array[j-1], array[j]
		}
	}
}

// InsertSortDemo 插入排序演示
func InsertSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	insertSort(copyArray)
	fmt.Println(copyArray)
}

// shellSort 希尔排序
func shellSort(array []int) {
	n := len(array)
	h := 1
	//寻找合适的间隔h
	for h < n/3 {
		h = 3*h + 1
	}
	for h >= 1 {
		//将数组变为间隔h个元素有序
		for i := h; i < n; i++ {
			//间隔h插入排序
			for j := i; j >= h && array[j] < array[j-h]; j -= h {
				array[j], array[j-h] = array[j-h], array[j]
			}
		}
		h /= 3
	}
}

// ShellSortDemo 希尔排序演示
func ShellSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	shellSort(copyArray)
	fmt.Println(copyArray)
}

// selectionSort 选择排序
func selectionSort(array []int, start int) {
	if start == len(array) {
		return
	}
	minIndex := start
	minVal := array[start]

	for i := start + 1; i < len(array); i++ {
		if array[i] < minVal {
			minIndex, minVal = i, array[i]
		}
	}
	array[start], array[minIndex] = array[minIndex], array[start]
	selectionSort(array, start+1)
}

// SelectionSortDemo 选择排序演示
func SelectionSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	selectionSort(copyArray, 0)
	fmt.Println(copyArray)
}

// heapSort 堆排序
func heapSort(array []int) {
	// array[0]不用,实际元素数量和最后一个元素的角标都为n
	n := len(array) - 1

	for k := n / 2; k >= 1; k-- {
		sinkHeapSort(array, k, n)
	}
	// 下沉排序
	for n > 1 {
		// 将大的放在数组后面,升序排序
		array[1], array[n] = array[n], array[1]
		n--
		sinkHeapSort(array, 1, n)
	}
}

// sinkHeapSort 下沉堆排序(由上往下的堆有序化)
func sinkHeapSort(array []int, k, n int) {
	for {
		i := 2 * k
		if i > n {
			break
		}
		// 选择较大的子节点
		if i < n && array[i+1] > array[i] {
			i++
		}
		// 没下沉到底就构造好堆了
		if array[k] >= array[i] {
			break
		}
		array[k], array[i] = array[i], array[k]
		k = i
	}
}

// HeapSortDemo 堆排序演示
func HeapSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	heapSort(copyArray)
	fmt.Println(copyArray)
}

// merge 归并
func merge(array []int, low, mid, high int, tmp []int) {
	i := 0
	j, k := low, mid+1
	for j <= mid && k <= high {
		if array[j] < array[k] {
			tmp[i] = array[j]
			i++
			j++
		} else {
			tmp[i] = array[k]
			i++
			k++
		}
	}

	for j <= mid {
		tmp[i] = array[j]
		i++
		j++
	}
	for k <= high {
		tmp[i] = array[k]
		i++
		k++
	}

	for t := 0; t < i; t++ {
		array[low+t] = tmp[t]
	}
}

func mergeSort(array []int, low, high int, tmp []int) {
	if low < high {
		mid := (low + high) / 2
		// 对左边序列进行归并排序
		mergeSort(array, low, mid, tmp)
		// 对右边序列进行归并排序
		mergeSort(array, mid+1, high, tmp)
		// 合并两个有序序列
		merge(array, low, mid, high, tmp)
	}
}

// MergeSortDemo 归并排序演示
func MergeSortDemo() {
	copyArray := make([]int, len(defaultArray))
	copy(copyArray, defaultArray)
	tmp := make([]int, len(defaultArray))
	mergeSort(copyArray, 0, len(copyArray)-1, tmp)
	fmt.Println(copyArray)
}
